C++中的unordered_map容器详解

C++中的unordered_map容器详解

1.unordered_map概述

unordered_map是C++11引入的关联容器，基于哈希表实现，存储键值对（key-value pairs），提供快速的查找、插入和删除操作，平均时间复杂度为O(1)O(1)O(1)。

2. 基本特性

• 哈希表实现：使用哈希函数组织键值对
• 唯一键：每个键只能出现一次
• 无序存储：元素不以任何特定顺序存储
• 快速访问：平均情况下提供常数时间复杂度的查找
• 动态大小：可以根据需要自动扩展

3. 头文件与声明

#include<unordered_map>usingnamespacestd;unordered_map<int,string>um1;// 空unordered_mapunordered_map<string,double>um2={{"pi",3.14},{"e",2.71}};// 初始化列表unordered_map<char,int>um3(10);// 初始桶数为10

4. 构造函数与初始化

4.1 默认构造

unordered_map<string,int>wordCount;

4.2 范围构造

pair<string,int>arr[]={{"apple",5},{"banana",3}};unordered_map<string,int>fruitCount(arr,arr+2);

4.3 拷贝构造

unordered_map<string,int>um2(um1);

4.4 自定义哈希函数和相等比较

structCaseInsensitiveHash{size_toperator()(conststring&s)const{size_t h=0;for(charc:s){h+=tolower(c);}returnh;}};structCaseInsensitiveEqual{booloperator()(conststring&a,conststring&b)const{if(a.length()!=b.length())returnfalse;for(size_t i=0;i<a.length();++i){if(tolower(a[i])!=tolower(b[i]))returnfalse;}returntrue;}};unordered_map<string,int,CaseInsensitiveHash,CaseInsensitiveEqual>case_insensitive_map;

5. 容量操作

5.1size()

cout<<um.size();// 返回键值对数量

5.2empty()

if(um.empty()){cout<<"unordered_map is empty";}

5.3max_size()

cout<<um.max_size();// 返回可容纳的最大键值对数

6. 元素访问

6.1operator[]

um["apple"]=5;// 插入或修改键"apple"对应的值intcount=um["apple"];// 访问键"apple"对应的值

6.2at()

try{intval=um.at("orange");// 访问键"orange"对应的值(边界检查)}catch(constout_of_range&e){cerr<<"Key not found: "<<e.what()<<endl;}

6.3 迭代器访问

for(autoit=um.begin();it!=um.end();++it){cout<<it->first<<": "<<it->second<<endl;}

7. 修改操作

7.1insert()

um.insert({"banana",3});// 插入单个键值对um.insert({{"pear",2},{"orange",4}});// 插入初始化列表autoresult=um.insert(make_pair("apple",6));// 返回pair<iterator, bool>

7.2emplace()

autoresult=um.emplace("grape",7);// 原地构造键值对

7.3erase()

um.erase("apple");// 删除键"apple"对应的键值对autoit=um.find("banana");if(it!=um.end()){um.erase(it);// 通过迭代器删除}um.erase(um.begin(),um.end());// 删除范围

7.4clear()

um.clear();// 清空所有键值对

7.5swap()

unordered_map<string,int>um2;um.swap(um2);// 交换两个unordered_map

8. 查找操作

8.1find()

autoit=um.find("apple");// 返回指向键"apple"的迭代器if(it!=um.end()){cout<<"Found: "<<it->second;}

8.2count()

cout<<um.count("banana");// 返回键"banana"的数量(0或1)

8.3equal_range()

autorange=um.equal_range("apple");// 返回等于"apple"的键值对范围

9. 桶操作

9.1bucket_count()

cout<<um.bucket_count();// 返回桶的数量

9.2 `max_bucket_count()

cout<<um.max_bucket_count();// 返回最大桶数

9.3bucket_size()

cout<<um.bucket_size(2);// 返回第2个桶中的键值对数

9.4bucket()

cout<<um.bucket("apple");// 返回"apple"所在的桶索引

10. 哈希策略

10.1load_factor()

cout<<um.load_factor();// 返回负载因子(键值对数/桶数)

10.2max_load_factor()

cout<<um.max_load_factor();// 返回最大负载因子um.max_load_factor(0.75);// 设置最大负载因子

10.3rehash()

um.rehash(20);// 设置桶数为至少20

10.4reserve()

um.reserve(100);// 预留空间至少容纳100个键值对

11. 完整示例

#include<iostream>#include<unordered_map>#include<string>usingnamespacestd;intmain(){// 创建并初始化unordered_mapunordered_map<string,int>wordCount={{"apple",5},{"banana",3},{"orange",2}};// 插入元素wordCount.insert({"grape",4});wordCount.emplace("pear",1);wordCount["kiwi"]=6;// 使用operator[]插入// 修改元素wordCount["apple"]+=2;// 查找元素if(wordCount.find("banana")!=wordCount.end()){cout<<"Banana count: "<<wordCount["banana"]<<endl;}// 遍历unordered_mapcout<<"All word counts:"<<endl;for(constauto&pair:wordCount){cout<<pair.first<<": "<<pair.second<<endl;}// 删除元素wordCount.erase("orange");autoit=wordCount.find("pear");if(it!=wordCount.end()){wordCount.erase(it);}// 桶信息cout<<"\nBucket information:"<<endl;cout<<"Number of buckets: "<<wordCount.bucket_count()<<endl;cout<<"Current load factor: "<<wordCount.load_factor()<<endl;// 调整哈希表wordCount.rehash(10);cout<<"After rehash, bucket count: "<<wordCount.bucket_count()<<endl;// 容量信息cout<<"\nSize: "<<wordCount.size()<<endl;cout<<"Is empty: "<<(wordCount.empty()?"Yes":"No")<<endl;return0;}

12. 性能提示

1. 平均情况下查找、插入、删除时间复杂度为O(1)O(1)O(1)
2. 最坏情况下(哈希冲突严重)时间复杂度退化为O(n)O(n)O(n)
3. 负载因子过高会影响性能，可适时rehash()
4. 自定义键类型需要提供哈希函数和相等比较
5. 迭代器在插入操作后可能失效(重新哈希时)

13. 与map比较